package com.hutu;

import java.util.HashMap;

/**
 * 76. 最小覆盖子串
 * https://leetcode-cn.com/problems/minimum-window-substring/
 *
 * @author hutu
 * @date 2020/12/17 10:56 上午
 */
public class MinWindow {

    public static String minWindow(String s, String t) {
        if(s==null||t==null||s.length()==0||t.length()==0){
            return "";
        }
        char[] need = t.toCharArray();
        char[] sChars = s.toCharArray();

        HashMap<Character, Integer> needMap = new HashMap<>();
        for (char c : need) {
            needMap.put(c,needMap.getOrDefault(c,0)+1);
        }
        HashMap<Character, Integer> window = new HashMap<>();

        int left = 0, right = 0,valid = 0,start = 0,len = Integer.MAX_VALUE;
        while (right < s.length()){
            Character c = sChars[right];
            right++;
            if (needMap.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(needMap.get(c))){
                    valid++;
                }
            }
            // 相等了说明窗口满足了，开始缩小窗口
            while (valid == need.length){

                if (right-left<len){
                    len = right;
                    start = left;
                }
                Character d = sChars[left];
                left++;
                if (window.containsKey(d)&&needMap.containsKey(d)){

                        if (window.get(d) == 1) {
                            window.remove(d);
                            valid--;
                        } else {
                            window.put(d, window.get(d) - 1);
                        }
                }

            }

        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, len);
    }

    public static void main(String[] args) {
        String s = "abceeris";
        String t = "cir";
        System.out.println(minWindow(s,t));
    }
}
